/**
 电话号码的字母组合 ---【多集合】
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
2-abc 3-def 4-ghi 5-jkl 6-mno 7-pqrs 8-tuv 9-wxyz
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
 */

/**
 * k = digits.length 结果元素的个数，树的深度， 集合的个数
 * map记录多集合映射关系
 * 【终止条件】到达深度： path.length == k 
 * 【循环--横向】digits每个元素对应集合都是一层  === 每个集合都是一层
 * 层数:index; 号码digits[index]  集合：map[digits[index]]
 * 【递归--纵向】index+1 index是为了控制层级
 * 【边界处理】
 */
var letterCombinations = function(digits) {
  const map=['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  const result = [];
  const path = [];
  const k = digits.length;
  if(k == 0) return result;
  const backTracking = (index) => {
    if(path.length == k) { 
      result.push(path.join(''));
      return;
    }
    const letter = map[digits[index]];
    for(let i=0;i<letter.length;i++) {//每一层都从第一个开始匹配
      path.push(letter[i]);
      backTracking(index+1); //进入下一层用下一个集合
      path.pop();
    }
  }
  backTracking(0);
  return result;
};
const digits = "23";
console.log('电话号码的字母组合', letterCombinations('2'));